package org.example.sort;

import java.util.Arrays;

/**
 * Java 排序整理
 * @Author chaigq
 * @Date 2020/11/18 11:43 下午
 * @Version 1.0
 */
public class JavaSort {


    // TODO 归并排序
    public static void sort(int[] array, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        // 继续将数组进行拆分，拆分成最小单元
        sort(array, start, mid);
        sort(array, mid + 1, end);
        // 调用排序算法
        mergerSort(array, start, mid, end);
    }
    // 将两个有序序列归并为一个有序序列(二路归并),将最小单元进行合并
    public static void mergerSort(int[] array, int start, int mid, int end) {
        // 定义一个临时数组，用来存储排序后的结果
        int[] arr = new int[end + 1];
        // 临时索引
        int postion = start;
        // 左侧Index
        int leftIndex = start;
        // 右侧Index
        int rightIndex = mid + 1;
        // 取出最小值放入临时数组中
        while (start <= mid && rightIndex <= end){
            // 左侧大于右侧的时候，将小的放入到临时数组中
            if (array[start] > array[rightIndex]){
                arr[postion++] = array[rightIndex++];
            }else {
                arr[postion++] = array[start++];
            }
        }
        // 将左侧多余的数放入临时数组中
        while (start <= mid){
            arr[postion ++] = array[start ++];
        }
        // 将右侧多余的数放入临时数组中
        while (rightIndex <= end){
            arr[postion ++] = array[rightIndex ++];
        }
        // 将临时数组中的值copy到原数组中
        for (int i = leftIndex; i <= end; i ++){
            array[i] = arr[i];
        }
    }

    public static void main(String[] args) {
        int[] array = { 58, 48, 69, 87, 49, 59, 25, 35, 68, 48 };
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
}
